package leetcode;

import java.util.*;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-28 20:25
 **/
public class LeetCode472 {

    private Node root;

    public LeetCode472() {
        root = new Node(null);
    }

    public static void main(String[] args) {
        LeetCode472 code = new LeetCode472();
        code.findAllConcatenatedWordsInADict(new String[]{"cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"});
    }

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> list = new ArrayList<>();
        Arrays.sort(words, Comparator.comparingInt(String::length));

        for (int i = 0; i < words.length; ++i) {
            String word = words[i];
            //空单词直接跳过
            if (word.length() == 0) {
                continue;
            }

            //判断单词word是否为连接词
            if (dfs(word, 0)) {
                //是就添加到结果集中
                list.add(word);
            } else {
                //不是就添加到前缀树中
                insert(word);
            }
        }

        return list;
    }

    public void insert(String word) {
        int n = word.length();

        Node temp = root;
        for (int i = 0; i < n; i++) {
            char c = word.charAt(i);
            Node node = temp.children.get(c);
            if (node == null) {
                node = new Node(c);
                temp.children.put(c, node);
            }
            temp = node;
        }
        temp.isEnd = true;
    }

    /**
     * 递归判断某一个单词是否为连接词
     */
    public boolean dfs(String word, int start) {
        //如果单词word被遍历到结尾了,说明该单词是连接词
        if (word.length() == start) {
            return true;
        }

        int n = word.length();
        Node temp = root;
        for (int i = start; i < n; i++) {
            char c = word.charAt(i);
            Node node = temp.children.get(c);
            if (node == null) {
                return false;
            }

            if (node.isEnd) {
                //如果遍历到一个单词的结尾,就继续从i+1索引递归遍历,看是否存在单词拼成当前单词;
                if (dfs(word, i + 1)) {
                    return true;
                }
            }
            temp = node;
        }

        return false;
    }



    class Node {
        Character c;
        Map<Character, Node> children;
        boolean isEnd;
        public Node(Character c) {
            this.c = c;
            children = new HashMap<>();
        }
    }

}
